#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
    ListNode *partition(ListNode *head, int x)
    {
        bool flag = false;
        ListNode *dhead = new ListNode(0);
        dhead->next = head;
        ListNode *ptr = dhead, *pos = dhead, *pre = nullptr;
        while (ptr && ptr->next != nullptr)
        {
            if (ptr->next->val < x)
            {
                ListNode *tmp = ptr->next;
                ptr->next = ptr->next->next;
                tmp->next = pos->next;
                pos->next = tmp;
                pos = tmp;
            }
            else
                flag = true;
            pre = ptr;
            ptr = ptr->next;
        }
        if (flag == true && pre && ptr->next < x)
        {
            pre->next = nullptr;
            ptr->next = pos->next;
            pos->next = ptr;
        }
        return dhead->next;
    }
};